Câu chuyện của Heian Fūunden xoay quanh việc quỷ tộc Yamawarawa đột nhiên tạo phản, chống lại Triều đình, sau biến cố Taira no Masakado gây loạn 60 năm. Để bảo vệ kinh đô, quan Thái chính đại thần Fujiwara Michinaga ủy lại cho Âm Dương Sư Kamo Hiroyuki và Abe no Seimei thu thập tin tức, điều tra về sự việc này. Seimei cho hay người đệ tử thân tín của mình là Âm Dương Sư Ashiya Dōma đã bắt tay với tộc Yamawarawa và có khả năng sẽ gọi oan hồn của Taira no Masakado trở lại dương thế để tác oai tác quái. Taira no Masakado còn được gọi là Shōmon, là một tướng lãnh của Triều đình Heian nhưng sau tạo phản, bị hành hình và mang oán niệm với Triều đình. Để cứu kinh đô khỏi hiểm họa này, Seimei đã chỉ định thiếu niên Kagura ở đền thờ Kumano đi khắp các vùng miền của nước Nhật để ngăn chặn kế hoạch gọi hồn của quỷ tộc Yamawarawa.Thế lực thù địch chủ yếu trong Heian Fūunden là Yamawarawa, một tộc thiểu số sống bằng nghề bùa chú thời Heian, nhưng dần về sau được miêu tả như là lực lượng tà quỷ (Oni). Để chống lại bọn quỷ dữ, các Samurai sử dụng thanh kiếm của mình, các Âm Dương Sư sử dụng Shikigami, các tăng lữ phái Phật giáo Chân ngôn (Shingonshū) sử dụng Pháp ấn, các Shugenja thuộc phái Thiên Đài (Tendaishū) sử dụng pháp thuật và các vu nữ sử dụng pháp thuật hồi phục cùng bắt tay với nhau trong chuyến du hành của đại tướng Kagura.Trong game, người chơi bắt gặp rất nhiều nhân vật lịch sử như Minamoto no Raikō, Fujiwara no Sumitomo cùng tồn tại với các nhân vật không tưởng. Hư thực lẫn lộn là một điểm thú vị của Heian Fūunden. Ngoài ra, người chơi còn bắt gặp Thiên Hoàng Ichijō, Pháp Hoàng Kazan qua câu chuyện. Tuy không trực tiếp tham gia chiến đấu nhưng họ là những nhân vật quan trọng trong câu chuyện.